package org.example.algorithms;

public class NQueens {

    //皇后数
    static int QUEENS = 8;
    //下标表示行,值表示queen存储在哪一列
    int[] result = new int[QUEENS];

    /**
     * 在每行放置Queen
     *
     * @param row
     */
    public void setQueens(int row) {
        if (row == QUEENS) {
            printQueens();
            return;
        }

        for (int col = 0; col < QUEENS; col++) {
            if (isOk(row, col)) {
                result[row] = col;
                setQueens(row + 1);
            }
        }
    }

    /**
     * 打印输出
     */
    private void printQueens() {
        for (int i = 0; i < QUEENS; i++) {
            for (int j = 0; j < QUEENS; j++) {
                if (result[i] == j) {
                    System.out.print("Q| ");
                }
                else {
                    System.out.print("*| ");
                }
            }
            System.out.println();
        }
        System.out.println("---------------------");
    }

    /**
     * 判断是否可以放置
     *
     * @param row 行
     * @param col 列
     * @return
     */
    private boolean isOk(int row, int col) {
        int leftup = col - 1;
        int rightup = col + 1;

        for (int i = row - 1; i >= 0; i--) {
            if (result[i] == col) {
                return false;
            }

            if (leftup >=0 && result[i] == leftup) {
                return false;
            }

            if (rightup < QUEENS && result[i] == rightup) {
                return false;
            }

            leftup--;
            rightup++;
        }

        return true;
    }

    public static void main(String[] args) {
        NQueens queens = new NQueens();
        queens.setQueens(0);
    }

}
